package sjjg.tree;

public class RedBlackTree<key extends Comparable<key>,value> {
    private Node root;//根节点
    private int N;//节点个数
    private static final boolean RED=true;
    private static final boolean BLACK=false;
    class Node{
        private key key;
        private value value;
        private Node left;
        private Node right;
        private boolean color;//区别红黑节点

        public Node(key key, value value, Node left, Node right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
    private boolean isRed(Node x){
           if(x==null){
               return false;
           }
           return x.color==RED;
    }
    private Node rotateLeft(Node h){//左旋
         //记录h的右子树x
         Node x=h.right;
         //x的左子节点变为h的右子节点
         h.right=x.left;
         //让h成为x的左子节点
         x.left=h;
         //让x的color属性值变为h的color属性值
         x.color= h.color;
         //让h的color属性值变为红色
         h.color=RED;
          return x;
    }
    private Node rotateRight(Node h){
         //记录h的左子节点x
         Node x=h.left;
         //让x的右子节点成为h的左子节点
         h.left=x.right;
         //让h成为x的右子节点
         x.right=h;
         //让x的color属性值变为h的color属性值
        x.color= h.color;
        //让h的color属性值变为红色
        h.color=RED;
         return  x;
    }
    private void flipColors(Node h){
            //让h的左子节点和右子节点的属性值都变为黑色
            h.left.color=BLACK;
            h.right.color=BLACK;
            //让h节点的color属性值变为红色
            h.color=RED;
    }
    public void put(key key,value value){
        root=put(root,key,value);
    }

    private Node put(Node h, key key, value value) {
        if (h==null){
            return new Node(key,value,null,null);
        }
        //比较key值
        int compare = key.compareTo(h.key);
        if(compare<0){
            //递归调用进入左子树
            h.left=put(h.left,key,value);
        }else if (compare>0){
            //递归调用进入右子树
             h.right=put(h.right,key,value);
        }else {
            h.value=value;
        }
        //平衡红黑树
        if(isRed(h.right)&&!isRed(h.left)){//左旋
            h = rotateLeft(h);
        }
        if(isRed(h.left)&&isRed(h.left.left)){//右旋
            h=rotateRight(h);
        }
        if(isRed(h.left)&&isRed(h.right)){//颜色反转
            flipColors(h);
        }
        return h;
    }
    public value get(key key){
        value value=get(root,key);
        return value;
    }

    private value get(Node h, key key) {
        if(h==null){
            return null;
        }
        //比较key值
        int compare = key.compareTo(h.key);
        if(compare<0){
            //递归调用左子树寻找
           return get(h.left,key);
        }else if(compare>0){
            //递归调用右子树寻找
             return get(h.right,key);
        }else {
            return h.value;
        }
    }
    public int size(){
        return N;
    }

    public static void main(String[] args) {
        RedBlackTree<String, String> redBlackTree = new RedBlackTree<>();
        redBlackTree.put("1","朱传杰");
        redBlackTree.put("2","邹羽洁");
        redBlackTree.put("3","赵兴");
        redBlackTree.put("4","站赛风");
        redBlackTree.put("5","张亚丽");
        System.out.println(redBlackTree.get("1"));
        System.out.println(redBlackTree.get("2"));
        System.out.println(redBlackTree.get("3"));
        System.out.println(redBlackTree.get("4"));
        System.out.println(redBlackTree.get("5"));
    }

}
